/*
 * Copyright (C) 2008 by The Regents of the University of California
 * Redistribution of this file is permitted under the terms of the GNU
 * Public License (GPL).
 *
 * @author Junghoo "John" Cho <cho AT cs.ucla.edu>
 * @date 3/24/2008
 */
 
#include "BTreeIndex.h"
#include "BTreeNode.h"

using namespace std;

/*
 * BTreeIndex constructor
 */
BTreeIndex::BTreeIndex()
{
    rootPid = -1;
    isWriting = false;
    a.clear();
}

void BTreeIndex::clear()
{
	rootPid = -1;
	isWriting = false;
	a.clear();
}

void BTreeIndex::InsertNode()
{
	BTNode t;
	t.clear();
	t.setLoad(false);
	a.push_back(t);
}

/*
 * Open the index file in read or write mode.
 * Under 'w' mode, the index if (openRead == true)if (openRead == true)file should be created if it does not exist.
 * @param indexname[IN] the name of the index file
 * @param mode[IN] 'r' for read, 'w' for write
 * @return error code. 0 if no error
 */
RC BTreeIndex::open(const string& indexname, char mode)
{
	clear();
	int treeExists = pf.open(indexname + ".idx", 'r');
	if (treeExists == 0 && mode == 'r')
	{
		rootPid = 0;
		int size = pf.endPid();
		for (int i=0; i<size; i++) InsertNode();
		for (int i=0; i<size; i++) a[i].setLoad(false);
	}
	else if (treeExists == 0)
	{
		rootPid = 0;
		int size = pf.endPid();
		for (int i=0; i<size; i++)
		{
			BTNode t;
			t.read(i,pf);
			t.setLoad(true);
			a.push_back(t);
		}
		pf.close();
	}
	else
		rootPid = -1;

	if (mode == 'w')
	{
		int ret = pf.open(indexname + ".idx", 'w');
		if (ret == 0)
			isWriting = true;
	}
    return 0;
}

/*
 * Close the index file.
 * @return error code. 0 if no error
 */
RC BTreeIndex::close()
{
	if (isWriting)
	{
		for (int i=0; i<a.size(); i++)
			a[i].write(i, pf);
	}
	pf.close();
    return 0;
}

void BTreeIndex::refreshFather(int id)
{
	if (a[id].isLeaf())
		return;
	for (int i=0; i<=a[id].getKeyCount(); i++)
	{
		int pid = a[id].recordid[i].pid;
		a[pid].setFatherNodePtr(id);
	}
}

/*
 * Insert (key, RecordId) pair to the index.
 * @param key[IN] the key for the value inserted into the index
 * @param rid[IN] the RecordId for the record being inserted into the index
 * @return error code. 0 if no error
 */
RC BTreeIndex::insert(int key, const RecordId& rid)
{
	if (rootPid == -1)
	{
		rootPid = 0;
		InsertNode();
		a[rootPid].initializeRoot(rootPid, key, rid);
		return 0;
	}

	IndexCursor cursor;
	locate(key, cursor);
	int curId = cursor.pid;
	a[curId].insert(key, rid);
	if (a[curId].getKeyCount() <= BTNode::maxt + BTNode::maxt) return 0;

	while (a[curId].getKeyCount() > BTNode::maxt + BTNode::maxt)
	{
		int outkey = -1;
		if (curId == 0)
		{
			int leftId = a.size(), rightId = a.size() + 1;
			InsertNode();
			InsertNode();
			a[leftId].copy(a[curId]);
			a[leftId].insertAndSplit(a[rightId], outkey);
			a[leftId].setNextNodePtr(rightId);
			a[leftId].setFatherNodePtr(0);
			a[rightId].setFatherNodePtr(0);
			a[curId].initializeRoot(leftId, outkey, rightId);
			refreshFather(leftId);
			refreshFather(rightId);
		}
		else
		{
			int leftId = curId, rightId = a.size();
			InsertNode();
			int fatherId = a[leftId].getFatherPid();
			a[leftId].insertAndSplit(a[rightId], outkey);
			a[fatherId].insert(outkey, rightId);
			a[leftId].setNextNodePtr(rightId);
			refreshFather(rightId);
		}
		if (curId != 0)
			curId = a[curId].getFatherPid();
	}
	return 0;
}

/*
 * Find the leaf-node index entry whose key value is larger than or 
 * equal to searchKey, and output the location of the entry in IndexCursor.
 * IndexCursor is a "pointer" to a B+tree leaf-node entry consisting of
 * the PageId of the node and the SlotID of the index entry.
 * Note that, for range queries, we need to scan the B+tree leaf nodes.
 * For example, if the query is "key > 1000", we should scan the leaf
 * nodes starting with the key value 1000. For this reason,
 * it is better to return the location of the leaf node entry 
 * for a given searchKey, instead of returning the RecordId
 * associated with the searchKey directly.
 * Once the location of the index entry is identified and returned 
 * from this function, you should call readForward() to retrieve the
 * actual (key, rid) pair from the index.
 * @param key[IN] the key to find.
 * @param cursor[OUT] the cursor pointing to the first index entry
 *                    with the key value.
 * @return error code. 0 if no error.
 */
RC BTreeIndex::locate(int searchKey, IndexCursor& cursor)
{
	if (rootPid == -1)
		return -1;

	int curPid = rootPid;
	cursor.pid = 0;
	if (!a[curPid].hasLoad())
		a[curPid].read(curPid, pf);
	while (!a[curPid].isLeaf())
	{
		a[curPid].locateChildPtr(searchKey, cursor.pid);
		curPid = cursor.pid;
		if (!a[curPid].hasLoad())
			a[curPid].read(curPid, pf);
	}
	a[curPid].locate(searchKey, cursor.eid);
    return 0;
}

RC BTreeIndex::first(IndexCursor& cursor)
{
	if (rootPid == -1)
		return -1;
	int curPid = rootPid;
	cursor.pid = 0;
	if (!a[curPid].hasLoad())
		a[curPid].read(curPid, pf);
	while (!a[curPid].isLeaf())
	{
		cursor.pid = a[curPid].recordid[0].pid;
		curPid = cursor.pid;
		if (!a[curPid].hasLoad())
			a[curPid].read(curPid, pf);
	}
	cursor.eid = 0;
    return 0;
}

/*
 * Read the (key, rid) pair at the location specified by the index cursor,
 * and move foward the cursor to the next entry.
 * @param cursor[IN/OUT] the cursor pointing to an leaf-node index entry in the b+tree
 * @param key[OUT] the key stored at the index cursor location.
 * @param rid[OUT] the RecordId stored at the index cursor location.
 * @return error code. 0 if no error
 */
RC BTreeIndex::readForward(IndexCursor& cursor, int& key, RecordId& rid)
{
	if (cursor.pid < 0 || cursor.pid >= a.size())
		return -1;
	RecordFile rf;
	if (!a[cursor.pid].hasLoad())
		a[cursor.pid].read(cursor.pid, pf);
	int rc = a[cursor.pid].readEntry(cursor.eid, key, rid);
	if (rc != 0)
		return rc;
	if (cursor.eid + 1 >= a[cursor.pid].getKeyCount())
	{
		cursor.pid = a[cursor.pid].getNextNodePtr();
		cursor.eid = 0;
	}
	else
		cursor.eid++;
    return 0;
}
